package junior.其他;

public class No6 {
    //                  缺失数字
    //给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
    //进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

    //--------------------------------------------------------------------------------
    //                      两次遍历法：成功
    //想法：使用一个数组存放记录下标为i的元素是否出现了
    /*
    public int missingNumber(int[] nums) {
        boolean[] bp = new boolean[nums.length+1];

        for (int i = 0; i < nums.length; i++) {
            bp[nums[i]]  = true;
        }

        for (int i = 0; i < nums.length+1; i++) {
            if (!bp[i]){
                return i;
            }
        }

        return -1;
    }*/
    //--------------------------------------------------------------------------------


    //--------------------------------------------------------------------------------
    //                      进阶版：只用额外常数空间解决
    //想法：将0-n相加减去数组内的元素相加就是缺失的数字
    /*
    public int missingNumber(int[] nums){
        int sum = 0,nSum = 0;

        for (int i = 0; i < nums.length; i++) {
            nSum += i;
            sum += nums[i];
        }
        nSum += nums.length;

        return nSum - sum;
    }*/
    //----------------------------------------------------------------------------------


    //----------------------------------------------------------------------------------
    //                      位运算法
    //想法：使用异或运算，将数组中的数再加上从0-n这n+1个数，那么只有一个缺失的数只有一个，其余的数都有两个
    //根据异或的运算法则：a ^ a = 0 ; a ^ b ^ c = a ^ c ^ b; a ^ 0 = a;
    //最终只有出现一次的数会保留下来
    /*
    public int missingNumber(int[] nums){
        int xor = 0;

        for (int i = 0; i < nums.length; i++) {
            //由于数组下标从0开始，到 nums.length - 1 结束，所以要加到n就得写成 i + 1
            xor ^= nums[i] ^ (i + 1);
        }

        return xor;
    }*/
    //----------------------------------------------------------------------------------


    //----------------------------------------------------------------------------------
    //                      等差数列求和法
    //与全部加起来一样，只是这个是用等差数列求和公式来计算总和
    public int missingNumber(int[] nums){

        int nSum = nums.length * (1 + nums.length) /2;
        int sum = 0;

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        return nSum - sum;
    }
}
